package solutions.jianzhi;

import solutions.lib.BaseSolution;
import solutions.lib.ListNode;

import java.util.List;

/**
 * @author lizhidong
 * <a href="https://leetcode-cn.com/problems/lMSNwu/">25.链表数字相加</a>
 */
public class Solution25 extends BaseSolution {

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        int len1 = getLen(l1);
        int len2 = getLen(l2);
        use1 = len1 > len2;
        int o = add(l1, l2, len1, len2);
        if (o != 0) {
            ListNode h = new ListNode(o);
            h.next = use1 ? l1 : l2;
            return h;
        }
        return use1 ? l1 : l2;
    }

    boolean use1 = true;

    private int add(ListNode l1, ListNode l2, int len1, int len2) {
        if (l1 == null || l2 == null) {
            return 0;
        }
        if (len1 > len2) {
            int o = add(l1.next, l2, len1 - 1, len2);
            l1.val += o;
            o = l1.val / 10;
            l1.val %= 10;
            return o;
        } else if (len1 < len2) {
            int o = add(l1, l2.next, len1, len2 - 1);
            l2.val += o;
            o = l2.val / 10;
            l2.val %= 10;
            return o;
        } else {
            int o = add(l1.next, l2.next, len1 - 1, len2 - 1);
            ListNode a = use1 ? l1 : l2;
            ListNode b = !use1 ? l1 : l2;
            a.val += b.val + o;
            o = a.val / 10;
            a.val %= 10;
            return o;
        }
    }

    private int getLen(ListNode p) {
        int len = 0;
        while (p != null) {
            len++;
            p = p.next;
        }
        return len;
    }

    public static void main(String[] args) {
        Solution25 solution = new Solution25();
    }
}